#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

//1863.找出所有子集的异或总和再求和
//ret表示所有子集的异或总和
int ret1 = 0;
vector<int> path1;
//递归
void dfs1(vector<int>& nums,int i){
    //结束条件
    if(i==nums.size()){
        int cur = 0;
        for(auto num : path1){
            cur ^= num;
        }
        ret1 += cur;
        return;
    }

    //不选当前下标的值
    dfs1(nums, i + 1);

    //选当前下标的值
    path1.push_back(nums[i]);
    dfs1(nums, i + 1);
    //回溯
    path1.pop_back();
}
void dfs2(vector<int>& nums,int pos){
    //每次调用函数开始时，都要求出数组中的异或总和
    int cur = 0;
    for(auto num : path1){
        cur ^= num;
    }
    ret1 += cur;

    for (int i = pos; i < nums.size();i++){
        path1.push_back(nums[i]);
        dfs2(nums, i + 1);
        //回溯
        path1.pop_back();
    }
}
int subsetXORSum(vector<int>& nums){
    dfs1(nums, 0);
    return ret1;
}

//全排列2
vector<vector<int>> ret2;
vector<int> path2;
vector<bool> check;
//递归+回溯+剪枝
void dfs3(vector<int>& nums){
    //结束条件
    if(path2.size()==nums.size()){
        ret2.push_back(path2);
        return;
    }

    for (int i = 0; i < nums.size();i++){
        //剪枝
        //筛选不符合的分支
        //check[i]==true表示当前值已将使用过，或者
        //不能越界i!=0并且当前数和上一个数相同nums[i]=nums[i-1]并且上一个数还没有使用过check[i-1]==false
        /*
        if(check[i]==ture||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false)){
            continue;
        }
        path2.push_back(nums[i]);
        check[i] = true;
        dfs3(nums);

        path2.pop_back();
        check[i] = false;
        */

        //筛选符合的分支
        //check[i]==false表示当前值没有使用过，并且
        //i=0的情况或者当前值和上一个值不相同nums[i]!=nums[i-1]或者相同但是上一个值还没有使用过check[i-1]==false
        if(check[i]==false&&(i==0||nums[i]!=nums[i-1]||check[i-1]==false)){
            path2.push_back(nums[i]);
            check[i] = true;
            dfs3(nums);

            //回溯
            path2.pop_back();
            check[i] = false;
        }
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums){
    check.resize(nums.size());
    //先排序，在之后的当前数和上一个数比较相同用到
    //sort(nums.begin, nums.end());
    dfs3(nums);
    return ret2;
}


//17.电话号码的字母组合
//全局变量
vector<string> nums = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ret3;
string path3;
void dfs(string digits,int i){
    //结束条件
    if(path3.size()==digits.size()){
        ret3.push_back(path3);
        return;
    }

    for (; i < digits.size();i++){
        //获取当前对应的数字
        int m = digits[i] - '0';
        //获取对应数字的字符串
        string cur = nums[m];
        for (int j = 0; j < cur.size();j++){
            path3 += cur[j];
            dfs(digits, i + 1);

            //回溯
            path3.pop_back();
        }
    }
}
vector<string> letterCombinations(string digits){
    if(digits.empty()){
        return ret3;
    }
    dfs(digits, 0);
    return ret3;
}

//22.括号生成
//全局变量
vector<string> ret4;
string path4;
unordered_map<char, int> hash1;
void dfs5(int n){
    //结束条件
    if(hash1['(']==n&&hash1[')']==n){
        ret4.push_back(path4);
        return;
    }

    //剪枝
    if(hash1['(']<=n&&hash1['(']>=hash1[')']){
        //选左括号
        path4 += '(';
        hash1['(']++;
        dfs5(n);
        //回溯
        path4.pop_back();
        hash1['(']--;

        //选右括号
        path4 += ')';
        hash1[')']++;
        dfs5(n);
        path4.pop_back();
        hash1[')']--;
    }
}
vector<string> generateParenthesis(int n){
    dfs5(n);
    return ret4;
}


//77.组合
vector<vector<int>> ret5;
vector<int> path5;
void dfs6(int n,int k,int pos){
    //结束条件
    if(path5.size()==k){
        ret5.push_back(path5);
        return;
    }

    //剪枝，从上一个数后面选，不能从前面选
    for (int i = pos; i <= n;i++){
        path5.push_back(i);
        dfs6(n, k, i++);
        //回溯
        path5.pop_back();
    }
}
vector<vector<int>> combine(int n, int k){
    dfs6(n, k, 1);
    return ret5;
}

//494.目标和
//本道题注意一定要在数组中所有元素都加或者减完后才能判断是否需要结束返回
//不能出现中途等于目标值后就直接结束返回
int ret6 = 0;
int path6 = 0;
void dfs7(vector<int>& nums,int target,int i){
    //结束条件
    if(i==nums.size()){
        if(path6==target){
            ret6++;
        }
        return;
    }

    //选加法
    path6 += nums[i];
    dfs7(nums, target, i + 1);
    path6 -= nums[i];

    //选减法
    path6-=nums[i];
    dfs7(nums, target, i + 1);
    path6 += nums[i];
}
int findTargetSumWays(vector<int>& nums, int target){
    dfs7(nums,target,0);
    return ret6;
}

//39.组合总和
vector<vector<int>> ret7;
vector<int> path7;
int aim = 0;
int sum = 0;
void dfs8(vector<int>& candidates,int pos){
    //结束条件
    if(sum==aim){
        ret7.push_back(path7);
        return;
    }

    for(int i=pos;i<candidates.size();i++){
        //剪枝
        if(sum<aim){
            sum += candidates[i];
            path7.push_back(candidates[i]);

            dfs8(candidates, i);
            //回溯
            path7.pop_back();
            sum -= candidates[i];
        }
    }
}
void dfs9(vector<int>& candidates,int pos){
    //结束条件
    if(sum==aim){
        ret7.push_back(path7);
        return;
    }
    //剪枝
    if(sum>aim||pos==candidates.size()){
        return;
    }

    //每一层表示当前下标的值从0到k个能想加多少个
    for (int k = 0; k * candidates[i] <= aim;k++){
        if(k){
            sum += candidates[i];
            path7.push_back(candidates[i]);
        }
        dfs(candidates, pos + 1);
    }

    //回溯
    for (int k = 1; k * candidates[i] <= aim;k++){
        sum -= candidates[i];
        path7.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target){
    aim = target;
    dfs8(candidates, 0);
    return ret7;
}

int main(){
    vector<int> nums = {1,2,3,1};
    findTargetSumWays(nums,3);
    return 0;
}